Simple $S_r$-homotopy types of Hom complexes and box complexes associated to $r$-graphs

摘要

For a pair $(H_1,H_2)$ of graphs, Lov\'{a}sz introduced a polytopal complexcalled the Hom complex $\text{Hom}(H_1,H_2)$, in order to estimate topologicallower bounds for chromatic numbers of graphs. The definition is generalized tohypergraphs. Denoted by $K_r^r$ the complete $r$-graph on $r$ vertices. Givenan $r$-graph $H$, we compare $\text{Hom}(K_r^r,H)$ with the box complex$\mathsf{B}_{\text{edge}}(H)$, invented by Alon, Frankl and Lov\'{a}sz. Weverify that $\text{Hom}(K_r^r,H)$ and $\mathsf{B}_{\text{edge}}(H)$, both areequipped with right actions of the symmetric group on $r$ letters $S_r$, are ofthe same simple $S_r$-homotopy type.